package _2022.hot100._33_搜索旋转排序数组;

/**
 * @author： YHSimon
 * @date： 2022-04-07 14:59
 */
public class Solution {
    public int search(int[] nums,int target){
        int n=nums.length;
        if(n==0){
            return -1;
        }
        if(n==1){
            return nums[0]==target?0:-1;
        }
        int l=0,r=n-1;
        while (l<=r){
            int mid=(l+r)/2;
            if(nums[mid]==target){
                return mid;
            }
            //[0,mid]有序
            if(nums[0]<=nums[mid]){
                if(nums[0]<=target&&target<nums[mid]){
                    r=mid-1;
                }else{
                    l=mid+1;
                }
            //[mid,n-1]有序
            }else{
                if(nums[mid]<target&&target<=nums[n-1]){
                    l=mid+1;
                }else{
                    r=mid-1;
                }
            }
        }
        return -1;
    }

    public int binarySearch(int[] nums,int target){
        int l=0,r=nums.length-1;
        while(l<=r){
            int mid=(l+r)/2;
            if(nums[mid]==target){
                return mid;
            }else if(target<nums[mid]){
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.search(new int[]{1,3,5,7,8,10,33}, 13));
    }
}
